package com.leetcode.partition4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/8/28 8:49
 */
public class LC376摆动序列 {

    public static int wiggleMaxLength(int[] nums) {
        return dynamicProgramming(nums);
    }

    public static void main(String[] args) {
        int[] nums = {1, 17, 5, 10, 13, 15, 10, 5, 16, 8};
//        int[] nums = {84};
        System.out.println(wiggleMaxLength(nums));
    }

    private static int greedy(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int currentDiffer = 0;          //当前峰值
        int preDiffer = 0;      //前一段的峰值
        int answer = 1;
        for (int i = 1; i < nums.length; i++) {
            currentDiffer = nums[i] - nums[i - 1];
            //只有当前峰值和前一段峰值出现正负数差值才符合条件
            if ((currentDiffer > 0 && preDiffer <= 0) || (currentDiffer < 0 && preDiffer >= 0)) {
                answer++;
                preDiffer = currentDiffer;
            }
        }
        return answer;
    }

    private static int dynamicProgramming(int[] nums) {
        //对数组进行去重
        List<Integer> numsList = new ArrayList<>();
        numsList.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                numsList.add(nums[i]);
            }
        }
        if (numsList.size() <= 2) return numsList.size();
        int[] dp = new int[numsList.size()];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < numsList.size(); i++) {
            int cur = numsList.get(i) - numsList.get(i - 1);
            int pre = numsList.get(i - 1) - numsList.get(i - 2);
            if (cur * pre < 0) {
                dp[i] = dp[i - 1] + 1;
                continue;
            }
            dp[i] = dp[i - 1];
        }
        System.out.println(Arrays.toString(dp));
        return dp[numsList.size() - 1];
    }
}
